package cs271.examples.recursion;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Subsets {
	
	public static Integer first(List<Integer> list) {
		return list.get(0);
	}
	
	public static List<Integer> rest(List<Integer> list) {
		return list.subList(1, list.size());
	}
	
	
	public static List<List<Integer>> allSubsets(List<Integer> set) {
		if(set.size() == 0) {
			ArrayList<List<Integer>> subsets = 
				new ArrayList<List<Integer>>();
			subsets.add(set);
			return subsets;
		} else {
			Integer first = first(set);
			List<Integer> rest = rest(set);
			
			List<List<Integer>> restSubsets = allSubsets(rest);
			List<List<Integer>> restSubsetsWithFirst = allSubsets(rest);
			
			for(List<Integer> localset: restSubsetsWithFirst) {
				localset.add(first);
			}
			
			restSubsets.addAll(restSubsetsWithFirst);
			return restSubsets;
		}
	}

	public static void printSets(List<List<Integer>> sets) {
		for(List<Integer> set: sets) {
			System.out.print("{");
			for(Integer i: set) {
				System.out.print(i + ", ");
			}
			System.out.print("},");
			
		}
	}
	
	public static void main(String[] args) {
		List<Integer> list = new ArrayList<Integer>();
		list.add(1);
		list.add(2);
		list.add(3);
		
		printSets(allSubsets(list));
	}
	
	
}
